using ll = long long;
class Solution {
public:
    int maxPointsInsideSquare(vector<vector<int>>& points, string s) {
        int n = points.size();
        ll left = 0, right = 1'000'000'001, ans = 0;
        auto fun = [&](int mid) {
            set<char> ss;
            for (int i = 0; i < n; i++) {
                if (max(abs(points[i][0]), abs(points[i][1])) <= mid) {
                    if (ss.count(s[i])) {
                        return false;
                    } else {
                        ss.insert(s[i]);
                    }
                }
                // } else {
                //     ans = ss.size();
                //     return true;
                // }
            }
            ans = ss.size();
            return true;
        };
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (fun(mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
};

int n = 1e9 + 7;
using LL = long long;
class Solution {
public:
    int maxProfit(vector<int>& inventory, int orders) {
        int ans = 0, tmp = 0;
        int left = 0, right = *max_element(inventory.begin(), inventory.end());
        auto fun = [&](int mid) {
            tmp = 0;
            for (int i : inventory) {
                // get(i, mid);
                if(i > mid)
                    tmp += i - mid;
                if (tmp > orders) {
                    return false;
                }
            }
            return true;
        };
        while (left <= right) {
            int mid = (left + right) >> 1;
            // cout << left << ' ' << right << endl;
            if (fun(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 此时所有地方被用到的都还剩left个
        // cout << left << ' ' << right << endl;
        tmp = 0;
        for (int i : inventory) {
            if (i < left)
                continue;
            tmp += i - left;
            LL a = i + left + 1,b = i - left;
            a%2 == 0 ? a/=2 : b/=2;
            ans = ans + ((a%n) *(b%n)) %n;
            ans %= n;
            // ans = ans + ((LL)(i + left + 1)) * ((i - left)) / 2 % n;
        }
        ans = ans + ((LL)(orders - tmp)%n) * (left%n) % n;
        ans %= n;
        // cout << tmp << ' ' << endl;
        return ans;
    }
};